/FONT#1=BASL30/FONT#2=BASB30/FONT#3=NGR25/FONT#4=NGR20
␈↓↓␈↓α␈↓β␈↓∧␈↓α␈↓ ¬→STANFORD UNIVERSITY␈↓ ↓H
␈↓β␈↓ ¬_STANFORD, CALIFORNIA 94305␈↓ ↓H
␈↓∧COMPUTER SCIENCE DEPARTMENT␈↓ 
+   Telephone:␈↓ ↓H
␈↓ 
+415-497-4971␈↓ ↓H
␈↓↓␈↓ επJuly 11,1975␈↓ ↓H
␈↓ ↓H
␈↓ ↓H
␈↓ ↓H
Mr. Ken Bowman␈↓ ↓H
College Division␈↓ ↓H
McGraw-Hill Publishing Co.␈↓ ↓H
1221 Avenue of the Americas␈↓ ↓H
New York, N.Y. 10020␈↓ ↓H
␈↓ ↓H
␈↓ ↓H
Dear Mr. Bowman:␈↓ ↓H
␈↓ ↓H
␈↓ ↓HThis␈αletter␈αwill␈αhopefully␈αclarify␈αsome␈αof␈αour␈αdiscussion␈αabout␈αthe␈αmarket␈αand␈αpotential␈αof␈αmy␈αLISP␈↓ ↓H
␈↓ ↓Hmanuscript:␈α∞The␈α∞Anatomy␈α∞of␈α∞the␈α∞language␈α∞LISP␈α∞(tentative␈α∞title).␈α∞I␈α∞should␈α∞note␈α∞that␈α∞the␈α∞following␈↓ ↓H
␈↓ ↓Hdiscussion␈α∂reflects␈α∂the␈α∂structure␈α∂of␈α∂the␈α∂final␈α∂text␈α∞rather␈α∞than␈α∞the␈α∞current␈α∞manuscript.␈α∞Most␈α∞of␈α∞the␈↓ ↓H
␈↓ ↓Hdiscrepancies␈α
involve␈α
reorganization,␈α
rather␈α
than␈α
major␈α
modifications.␈↓ ↓H
␈↓ ↓H
␈↓ ↓HIn␈α∞its␈α∞most␈α∞obvious␈α∞application␈α∞the␈α∞book␈α∞represents␈α∞the␈α∞best␈α∞discussion␈α∞of␈α∞all␈α∞aspects␈α
of␈α
the␈α
LISP␈↓ ↓H
␈↓ ↓Hlanguage.␈α∂The␈α∞text␈α∞covers␈α∞the␈α∞programming␈α∞aspects,␈α∞introducing␈α∞structured␈α∞programming␈α∞through␈↓ ↓H
␈↓ ↓Hthe␈α⊃use␈α⊃of␈α⊃McCarthy's␈α⊃abstract␈α⊃syntax␈α⊃as␈α⊃it␈α⊃develops␈α⊃the␈α⊃techniques␈α⊂of␈α⊂recursive␈α⊂programming.␈↓ ↓H
␈↓ ↓HLISP's␈α∂list␈α∂notation␈α∂is␈α∂introduced␈α∂as␈α∂a␈α∂discussion␈α∞of␈α∞abstract␈α∞data␈α∞structures␈α∞and␈α∞the␈α∞problems␈α∞of␈↓ ↓H
␈↓ ↓Hrepresentation.␈αThe␈αuse␈αof␈αabstract␈αalgorithms␈αand␈αdata␈αstructures␈αis␈αan␈αexcellent␈αway␈αto␈αexplain␈αthe␈↓ ↓H
␈↓ ↓Htrue␈α
intent␈α
of␈α
structured␈α
programming;␈α
this␈α
approach␈α
will␈α
be␈α
strengthened␈α
in␈α
the␈α
next␈α
draft.␈↓ ↓H
␈↓ ↓H
␈↓ ↓HAfter␈α
the␈α
student␈α
has␈α
gained␈α
familarity␈α
with␈α
the␈α
basic␈α
properties␈α
of␈α
the␈α
language␈α
we␈α
introduce␈α
an␈↓ ↓H
␈↓ ↓Habstract␈α∃version␈α∃of␈α∃the␈α∃LISP␈α∃interpreter.␈α∃This␈α∃interpreter␈α∃clearly␈α∃demonstrates␈α∃the␈α∃power␈α∀of␈↓ ↓H
␈↓ ↓Habstraction␈α
and␈α
refinement␈α
in␈α
programming.␈α
The␈α
student␈α
is␈α
also␈α
given␈α
a␈α
precise␈αdescription␈αof␈αthe␈↓ ↓H
␈↓ ↓Hmeaning␈α
of␈αLISP␈αconstructs.␈αThe␈αdiscussion␈αof␈αthis␈αLISP␈αinterpreter␈αis␈αalso␈αquite␈αhelpful␈αin␈αgiving␈↓ ↓H
␈↓ ↓Hinsights␈α
into␈α
the␈α
probelematic␈α
areas␈α
of␈α
binding␈α
strategies.␈↓ ↓H
␈↓ ↓H
␈↓ ↓HThough␈α∂the␈α∂interpreter␈α∂is␈α∂an␈α∂accurate␈α∂description␈α∂of␈α∂LISP's␈α∂semantics,␈α∂the␈α∞level␈α∞of␈α∞description␈α∞is␈↓ ↓H
␈↓ ↓Hhigher␈α∩than␈α∩what␈α⊃one␈α⊃usually␈α⊃expects␈α⊃as␈α⊃a␈α⊃implementation.␈α⊃We␈α⊃remedy␈α⊃this␈α⊃next,␈α⊃beginning␈α⊃a␈↓ ↓H
␈↓ ↓Hdetailed␈α∞description␈α∞of␈α∞a␈α∞typical␈α∞LISP␈α∞implementation.␈α∞This␈α
is␈α
done␈α
in␈α
two␈α
phases:␈α
first,␈α
the␈α
static␈↓ ↓H
␈↓ ↓Hstructure␈α∩is␈α∩described.␈α∩This␈α⊃covers␈α⊃the␈α⊃storage␈α⊃conventions␈α⊃for␈α⊃Symbolic␈α⊃Expressions,␈α⊃the␈α⊃LISP␈↓ ↓H
␈↓ ↓Hprimitives,␈α∞the␈α∞storage␈α∞management␈α∞facilities,␈α∞and␈α∞two␈α∞common␈α∞strategies␈α∞for␈α
maintaining␈α
variable␈↓ ↓H
␈↓ ↓Hbindings.␈α
This␈α
section␈α
gives␈α
motivation␈αfor␈αmany␈αof␈αthe␈αtypical␈αalgorithms␈αand␈αdata␈αrepresentation␈↓ ↓H
␈↓ ↓Hwhich␈α
are␈αcurrently␈αstudied␈αin␈αdata␈αstructures␈αcourses.␈αMy␈αpast␈αexperience␈α(teaching␈αat␈αUCLA,␈αUC␈↓ ↓H
␈↓ ↓HSanta␈α
Cruz,␈α
Stanford,␈α
and␈α
San␈α
Jose␈α
State)␈α
has␈α
been␈α
that␈α
motivation␈α
is␈α
weak␈α
in␈α
many␈α
current␈α
texts.␈↓ ↓H
␈↓ ↓H
␈↓ ↓HThe␈α
second␈α
phase␈α
of␈α
LISP␈αimplementation␈αcovers␈αthe␈αdynamic␈αstructure␈αof␈αLISP:␈αhow␈αrecursion␈αis␈↓ ↓H
␈↓ ↓Himplemented,␈α∞how␈α∞environments␈α∞are␈α∞maintained,␈α∞how␈α∞running␈α∞and␈α
debugging␈α
in␈α
LISP␈α
(or␈α
indeed␈↓ ↓H
␈↓ ↓Hany␈α
good␈α
on-line␈α
language)␈α
is␈α
usually␈α
done.␈α
This␈α
section␈α
also␈α
discusses␈α
compilation␈α
and␈α
gives␈α
abstract␈↓ ↓H
␈↓ ↓Hcompilers␈α⊂for␈α⊂various␈α⊂subsets␈α⊂of␈α⊂LISP.␈α⊂Since␈α⊂the␈α⊂student␈α⊂understands␈α⊂the␈α⊂structure␈α⊂of␈α⊂the␈α∂LISP␈↓ ↓H
␈↓ ↓Hinterpreter,␈α∩the␈α∩compiling␈α∩algorithms␈α∩are␈α∩easily␈α∩assimilated␈α∩now.␈α∩The␈α∩purpose␈α⊃and␈α⊃structure␈α⊃of␈↓ ↓H
␈↓ ↓Hcompilers␈α
is␈α
most␈α
lucidly␈α
demonstrated␈α
by␈α
seeing␈αa␈αcompilation␈αalgorithm␈αexpressed␈αin␈αLISP.␈αOnce␈↓ ↓H
␈↓ ↓Hstudents␈α
understand␈αthe␈αbasic␈αalgorithms␈αthey␈αtypically␈αare␈αable␈αto␈αextend␈αthem␈αto␈αlarger␈αlanguages␈↓ ↓H
␈↓ ↓Hor␈αimprove␈αthem␈αfor␈αmore␈α
efficient␈α
code.␈α
This␈α
section␈α
also␈α
covers␈α
one-pass␈α
assemblers,␈α
bootstrapping,␈↓ ↓H
␈↓ ↓Hand␈α
will␈α
soon␈α
do␈α
more␈α
with␈α
code␈α
optimization.␈↓ ↓H
␈↓ ↓H
␈↓ ↓HThe␈α∀section␈α∀on␈α∀"Storage␈α∀Structures␈α∀and␈α∀Efficiency"␈α∀begins␈α∀a␈α∀more␈α∀typical␈α∀discussion␈α∪of␈α∪data␈↓ ↓H
␈↓ ↓Hstructures,␈αbut␈αuses␈αthe␈αintuitions␈αgained␈αin␈αthe␈α
prior␈α
sections␈α
to␈α
motivate␈α
the␈α
study␈α
of␈α
vectors,␈α
arrays␈↓ ↓H
␈↓ ↓Hand␈αstring␈αprocessors.␈αThis␈αsection␈αalso␈αintroduces␈αseveral␈αof␈α
LISP's␈α
pointer␈α
manipulation␈α
operations␈↓ ↓H
␈↓ ↓Has␈αdevices␈αto␈αimprove␈αefficiency.␈αNotice␈αthat␈αthe␈αstyle␈αof␈αthe␈αtext␈αis␈αfrom␈αthe␈αabstract␈αto␈αthe␈α
concrete.␈↓ ↓H
␈↓ ↓HThe␈αearly␈αsections␈αdeal␈αin␈αabstract␈αalgorithms␈αand␈αdata␈α
structures.␈α
The␈α
notation␈α
is␈α
mathematical␈α
and␈↓ ↓H
␈↓ ↓Hhigh-level.␈α⊃This␈α⊃gives␈α⊃a␈α⊃very␈α⊂concise␈α⊂way␈α⊂of␈α⊂expressing␈α⊂complex␈α⊂algorithms.␈α⊂As␈α⊂the␈α⊂lower␈α⊂level␈↓ ↓H
␈↓ ↓Hreprsentations␈α⊂are␈α⊂specified␈α⊂the␈α⊂algorithm␈α⊂becomes␈α⊂bulkier␈α⊂but␈α⊂not␈α⊂more␈α⊂difficult␈α∂to␈α∂understand.␈↓ ↓H
␈↓ ↓HThus␈αthe␈αabstract␈αLISP␈αinterpreter␈αis␈αquite␈αunderstandable␈αindependent␈αof␈αhow␈αit␈αwill␈αbe␈αcoded␈αfor␈↓ ↓H
␈↓ ↓Ha␈α
specific␈α
machine.␈α
Later,␈α
as␈α
we␈α
map␈α
LISP␈α
onto␈α
a␈α
typical␈α
machine,␈αthe␈αlevel␈αof␈αdetail␈αwill␈αincrease␈↓ ↓H
␈↓ ↓Hbut␈α⊃by␈α⊃that␈α⊂time␈α⊂the␈α⊂student␈α⊂will␈α⊂already␈α⊂understand␈α⊂the␈α⊂interpreter␈α⊂as␈α⊂a␈α⊂LISP␈α⊂algorithm.␈α⊂The␈↓ ↓H
␈↓ ↓Hsection␈α
on␈α
"Storage␈α
Structures␈α
and␈α
Efficiency"␈α
is␈α
even␈α
more␈α
concrete,␈α
analyzing␈α
alternative␈α
ways␈αof␈↓ ↓H
␈↓ ↓Hstoring␈α⊗data␈α⊗and␈α⊗studying␈α⊗several␈α⊗algorithms␈α⊗which␈α∃can␈α∃improve␈α∃efficiency␈α∃through␈α∃pointer␈↓ ↓H
␈↓ ↓Hmanipulation.␈↓ ↓H
␈↓ ↓H
␈↓ ↓HThe␈α⊂final␈α⊂section␈α⊂on␈α∂the␈α∂"Implications␈α∂of␈α∂LISP"␈α∂will␈α∂discuss␈α∂a␈α∂variety␈α∂of␈α∂topics␈α∂under␈α∂two␈α∂basic␈↓ ↓H
␈↓ ↓Hheadings.␈αFirst,␈αthe␈αpractical␈αimplications␈αto␈αlanguage␈αdesign;␈αafter␈αsuch␈α
a␈α
complete␈α
analysis␈α
of␈α
LISP,␈↓ ↓H
␈↓ ↓Hwe␈αare␈αable␈αto␈αsee␈αmany␈αweaknesses␈αboth␈αin␈αLISP␈αand␈αin␈αseveral␈αmore␈αrecent␈αendeavors.␈αWe␈α
discuss␈↓ ↓H
␈↓ ↓Hthe␈α∞the␈α∞lessons␈α∞that␈α∞can␈α∞be␈α∞learned␈α∞from␈α∞fifteen␈α∞years␈α∞of␈α∞experience␈α∞with␈α
LISP.␈α
The␈α
second␈α
topic␈↓ ↓H
␈↓ ↓Hinvolves␈α_LISP␈α_and␈α_its␈α_theoretical␈α_implications␈α_in␈α_the␈α↔mathematical␈α↔theory␈α↔of␈α↔computation.␈↓ ↓H
␈↓ ↓HMcCarthy's␈α∃work␈α∃on␈α∃LISP␈α∃was␈α∃one␈α∃of␈α∃the␈α∃first␈α∃attempts␈α∃to␈α∃bring␈α∃a␈α∃mathematical␈α∃rigor␈α∀to␈↓ ↓H
␈↓ ↓Hprogramming.␈αWhat␈αwe␈αwill␈αdo␈αhere␈αis␈αrelate␈αthe␈αmore␈αtraditional␈αstudies␈αof␈αmathematical␈αlogic␈αand␈↓ ↓H
␈↓ ↓Hrecursion␈α⊃theory␈α⊃to␈α⊃computer␈α⊃science.␈α⊃This␈α⊃will␈α⊃involve␈α⊂a␈α⊂careful␈α⊂analysis␈α⊂of␈α⊂the␈α⊂three␈α⊂ideas␈α⊂of␈↓ ↓H
␈↓ ↓Hcomputation,␈αdeduction,␈αand␈αtruth.␈αThis␈αrelates␈αLISP␈αto␈αthe␈αrecent␈αwork␈αof␈αD.␈αScott,␈αC.␈αWadsworth,␈↓ ↓H
␈↓ ↓Hand␈αM.␈αGordon.␈αSome␈αof␈αthis␈αmaterial␈αis␈αin␈αthe␈αcurrent␈αmanuscript␈αbut␈αspread␈α
out␈α
and␈α
in␈α
very␈α
poor␈↓ ↓H
␈↓ ↓Hshape.␈α∞I␈α∞have␈α∞been␈α∞teaching␈α∞a␈α∞graduate␈α∞seminar␈α∞this␈α
summer␈α
on␈α
just␈α
this␈α
subject␈α
so␈α
revision␈α
and␈↓ ↓H
␈↓ ↓Hincorporation␈α
will␈α
be␈α
minor.␈↓ ↓H
␈↓ ↓H
␈↓ ↓HJudging␈α
from␈α
the␈α
reaction␈α
to␈α
the␈α
text,␈α
both␈α
in␈α
the␈αreseach␈αcommunity␈αand␈αfrom␈αstudents␈αI␈αbelieve,␈↓ ↓H
␈↓ ↓Hthe␈αtext␈αwill␈αsell␈αvery␈αwell.␈αTo␈αmy␈αknowledge␈α
there␈α
is␈α
currently␈α
no␈α
text␈α
which␈α
covers␈α
the␈α
broad␈α
range␈↓ ↓H
␈↓ ↓Hof␈α∞topics␈α∞in␈α∞such␈α∞a␈α∞unified␈α∞manner.␈α∞Students␈α∞of␈α∞mine␈α∞who␈α∞have␈α
gone␈α
on␈α
to␈α
more␈α
advanced␈α
work␈↓ ↓H
␈↓ ↓Hhave␈α⊃commented␈α⊃on␈α⊃the␈α⊃benefits␈α⊃of␈α⊃having␈α⊃a␈α⊃clear␈α⊃understanding␈α⊃of␈α⊃the␈α⊃relationships␈α⊂between␈↓ ↓H
␈↓ ↓Hvarious␈α≤aspects␈α≤of␈α≤the␈α≤field.␈α≤Indeed␈α≤I␈α≤feel␈α≠that␈α≠there␈α≠is␈α≠a␈α≠premature␈α≠fragmenting␈α≠or␈↓ ↓H
␈↓ ↓Hdepartmentalization␈α
of␈α
computer␈α
science.␈α
This␈α
text␈α
is␈α
an␈α
attempt␈α
to␈α
reverse␈α
that␈α
trend.␈↓ ↓H
␈↓ εW
␈↓ εW
Yours sincerely,␈↓ εW
␈↓ εW
␈↓ εW
␈↓ εW
John R. Allen␈↓ εW
Research Associate␈↓ εW
Computer Science Dept␈↓ εW
Artificial Intelligence Lab␈↓ εW
␈↓ εW
␈↓ ↓H